9435. CodeCoder против TopForces

 

Соревновательное программирование очень популярно в Byteland. Фактически, каждый гражданин Байтландии зарегистрирован на двух сайтах программирования – CodeCoder и TopForces. Каждый сайт поддерживает свою собственную рейтинговую систему. Каждый гражданин имеет уникальный целочисленный рейтинг на каждом сайте, который приблизительно соответствует их навыкам. Чем выше рейтинг, тем лучше навык.

Люди Byteland от природы оптимистичны. Гражданин A думает, что у него есть шанс победить гражданина B в соревновании по программированию, если существует последовательность граждан Байтландии A = P0, P1, ..., Pk = B для некоторого k ≥ 1 такого, что для каждого i (0 ≤ i < k), Pi имеет более высокий рейтинг, чем Pi+1 на одном или обоих сайтах.

Каждый гражданин Байтландии хочет знать, сколько других граждан он может победить в соревновании по программированию.

 

Вход. В первой строке записано целое число n (1 ≤ n ≤ 100 000) – количество горожан. Следующие n строк содержат информацию о рейтингах. i - ая строка содержит два целых числа CСi и TFi – рейтинги i - го гражданина на CodeCoder и TopForces (1 ≤ CCi, TFi ≤ 106). Все рейтинги на каждом сайте разные.

 

Выход. Для каждого гражданина i выведите целое число bi – сколько других граждан они могут победить в соревновании по программированию. Каждое значение bi должно быть выведено в отдельной строке в том порядке, в котором граждане указаны во входных данных.

 

Пример входа

Пример выхода

4

2 3

3 2

1 1

4 5

2

2

0

3

 

 

РЕШЕНИЕ

графы – поиск в глубину

 

Анализ алгоритма

Пронумеруем граждан от 0 до n – 1. Отсортируем людей по рейтингу CodeCoder, и по рейтингу TopForces. Построим граф из n вершин, соответствующим n гражданам. Проведем ориентированное ребро u → v если u может победить v по рейтингу CodeCoder или TopForces, при этом граждане u и v стоят рядом в одном из отсортированных списков.

Далее задачу можно решить за O(n2). Ответом для каждой вершины v будет число вершин, посещенных в результате поиска в глубину dfs(v) без учета самой вершины v. Однако для n ≤ 100 000 это решение не пройдет по времени.

Пусть p0, p1, …, pn-1 – номера граждан в порядке возрастания их рейтинга CodeCoder. Совершим n запусков поиска в глубину в порядке dfs(p0), dfs(p1), …, dfs(pn-1). Изначально обнулим массив used. При запуске dfs(pi) не обнуляем массив used. В таком случае поиск начнется с pi и пройдет только по тем вершинам, достижимым из pi, которые раньше не были посещены. Следовательно сложность n поисков в глубину составит O(n), так как каждая вершина будет посещена только один раз в одном из поисков в глубину. В переменной cnt подсчитываем количество посещенных вершин (для которых used[i] = 1). После вызова dfs(pi) значение cnt – 1 содержит число граждан, которое сможет победить человек i в соревновании по программированию.

 

Пример

Рассмотрим первый тест. Отсортируем людей по рейтингам CodeCoder и TopForces. Возле рейтинга указан номер гражданина.

 

Граф зависимостей имеет вид:

Запустим поиск в глубину из кажой вершины и запишем множество вершин, достижимых из нее. Вершины перебираем в порядке возрастания их рейтинга CodeCoder.

·        dfs(2): used = {2}, |used| – 1 = 0;

·        dfs(0): used = {0, 1, 2}, |used| – 1 = 2;

·        dfs(1): used = {0, 1, 2}, |used| – 1 = 2;

·        dfs(3): used = {0, 1, 2, 3}, |used| – 1 = 3;

 

Рассмотрим следующий тест.

 

8

325852 616191

656540 952031

407005 621970

30613 174333

888502 961606

530744 986735

843613 956344

394581 202693

 

Пронумеруем граждан от 0 до 7. Слева отсортируем людей по рейтингу CodeCoder, справа – по TopForces. Возле рейтинга укажем номер гражданина.

 

 

Изобразим граф зависимостей.

 

 

Реализация алгоритма

Объявим рабочие массивы. В массивах a и b храним пары (рейтинг, номер гражданина) соответственно для CodeCoder и для TopForces.

 

vector<pair<int, int>> a, b;

vector<int> used, res;

vector<vector<int>> g;

 

Функция dfs реализует поиск в глубину из вершины v. В переменной cnt подсчитывается количество посещенных вершин.

 

void dfs(int v)

{

  used[v] = 1;

  cnt++;

  for (int to : g[v])

    if (used[to] == 0) dfs(to);

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d", &n);

for (i = 0; i < n; i++)

{

  scanf("%d %d", &x, &y);

  a.push_back(make_pair(x, i));

  b.push_back(make_pair(y, i));

}

 

Сортируем массивы по возрастанию рейтига.

 

sort(a.begin(), a.end());

sort(b.begin(), b.end());

 

Строим граф из n вершин. Проводим ориентированное ребро u → v если u может победить v и при этом граждане u и v стоят рядом в любом из отсортированных списков.

 

g.resize(n);

for (i = 1; i < n; i++)

{

  g[a[i].second].push_back(a[i - 1].second);

  g[b[i].second].push_back(b[i - 1].second);

}

 

Перебираем вершины графа – граждан в порядке возрастания их рейтинга CodeCoder (массив а). В переменной cnt подсчитываем количество вершин, в которые можно попасть из v.

 

res.resize(n);

used.resize(n);

cnt = 0;

for (i = 0; i < n; i++)

{

  v = a[i].second;

  if (used[v] == 0) dfs(v);

  res[v] = cnt - 1;

}

 

Выводим ответ.

 

for (i = 0; i < n; i++)

  printf("%d\n", res[i]);